﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace testPrj
{
    class SortedMatrix
    {
        private int[,] sortedMatrix;
        private int size;
        public SortedMatrix(int n, int[,] matrix)
        {
            this.size = n;
            this.sortedMatrix = matrix;
        }

        public bool Find(int targetValue)
        {
            if (targetValue < sortedMatrix[0, 0] || targetValue > sortedMatrix[size - 1, size - 1])
            {
                return false; //can not find it
            }

            int row = 0;
            int col = size - 1;
            while (row < size && col >= 0)
            {
                if (sortedMatrix[row, col] < targetValue)
                {
                    ++row;
                }
                else if (sortedMatrix[row, col] > targetValue)
                {
                    --col;
                }
                else
                {
                    return true;
                }
            }
            //can not fine
            return false;
        }

        #region Test
        public static void Test()
        {
            const int n = 5;
            int[,] matrix = new int[n, n]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
            };

            var sm = new SortedMatrix(n, matrix);
            if (sm.Find(13))
            {
                Console.WriteLine("Pass test on 13");
            }
            else
            {
                Console.WriteLine("Failed on test on 13");
            }

            if (!sm.Find(25))
            {
                Console.WriteLine("Pass test on 25");
            }
            else
            {
                Console.WriteLine("Failed on test on 25");
            }
        }
        #endregion
    }
}
